package hwThree1;

/******************************************************************************
 *  Compilation:  javac BinarySearchST.java
 *  Execution:    java BinarySearchST
 *  Dependencies: StdIn.java StdOut.java
 *  Data files:   https://algs4.cs.princeton.edu/31elementary/tinyST.txt
 *
 *  Symbol table implementation with binary search in an ordered array.
 *
 *  % more tinyST.txt
 *  S E A R C H E X A M P L E
 *
 *  % java BinarySearchST < tinyST.txt
 *  A 8
 *  C 4
 *  E 12
 *  H 5
 *  L 11
 *  M 9
 *  P 10
 *  R 3
 *  S 0
 *  X 7
 *
 ******************************************************************************/

/**
 *  The {@code BST} class represents an ordered symbol table of generic
 *  key-value pairs.
 *  It supports the usual <em>put</em>, <em>get</em>, <em>contains</em>,
 *  <em>delete</em>, <em>size</em>, and <em>is-empty</em> methods.
 *  It also provides ordered methods for finding the <em>minimum</em>,
 *  <em>maximum</em>, <em>floor</em>, <em>select</em>, and <em>ceiling</em>.
 *  It also provides a <em>keys</em> method for iterating over all of the keys.
 *  A symbol table implements the <em>associative array</em> abstraction:
 *  when associating a value with a key that is already in the symbol table,
 *  the convention is to replace the old value with the new value.
 *  Unlike {@link java.util.Map}, this class uses the convention that
 *  values cannot be {@code null}—setting the
 *  value associated with a key to {@code null} is equivalent to deleting the key
 *  from the symbol table.
 *  <p>
 *  It requires that
 *  the key type implements the {@code Comparable} interface and calls the
 *  {@code compareTo()} and method to compare two keys. It does not call either
 *  {@code equals()} or {@code hashCode()}.
 *  <p>
 *  This implementation uses a <em>sorted array</em>.
 *  The <em>put</em> and <em>remove</em> operations take &Theta;(<em>n</em>)
 *  time in the worst case.
 *  The <em>contains</em>, <em>ceiling</em>, <em>floor</em>,
 *  and <em>rank</em> operations take &Theta;(log <em>n</em>) time in the worst
 *  case.
 *  The <em>size</em>, <em>is-empty</em>, <em>minimum</em>, <em>maximum</em>,
 *  and <em>select</em> operations take &Theta;(1) time.
 *  Construction takes &Theta;(1) time.
 *  <p>
 *  For alternative implementations of the symbol table API,
 *  see {@link ST}, {@link BST}, {@link SequentialSearchST}, {@link RedBlackBST},
 *  {@link SeparateChainingHashST}, and {@link LinearProbingHashST},
 *  For additional documentation,
 *  see <a href="https://algs4.cs.princeton.edu/31elementary">Section 3.1</a> of
 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 */
import java.util.Arrays;

public class BinarySearchSTItem<Key extends Comparable<Key>, Value> {
    private Item<Key, Value>[] items; // 保存键值对的数组
    private int n = 0; // 当前符号表中键值对的数量

    // Item 类表示键值对
    public static class Item<Key, Value> {
        public Key key;
        public Value value;

        public Item(Key key, Value value) {
            this.key = key;
            this.value = value;
        }
    }

    // 默认构造函数
    public BinarySearchSTItem() {
        items = (Item<Key, Value>[]) new Item[2]; // 初始化容量为2
    }

    // 构造函数，接受一个 Item 数组并将其归并排序
    public BinarySearchSTItem(Item<Key, Value>[] inputItems) {
        this.items = Arrays.copyOf(inputItems, inputItems.length); // 复制数组
        this.n = items.length; // 更新键值对数量
        mergeSort(items, 0, items.length - 1); // 对数组进行归并排序
    }

    // 获取符号表中的键值对数量
    public int size() {
        return n;
    }

    // 判断符号表是否为空
    public boolean isEmpty() {
        return n == 0;
    }

    // 根据键获取值
    public Value get(Key key) {
        if (key == null) throw new IllegalArgumentException("Key cannot be null");
        int i = rank(key);
        if (i < n && items[i].key.equals(key)) {
            return items[i].value;
        }
        return null;
    }

    // 插入或更新键值对
    public void put(Key key, Value value) {
        if (key == null) throw new IllegalArgumentException("Key cannot be null");

        int i = rank(key); // 找到键的插入位置
        if (i < n && items[i].key.equals(key)) {
            // 如果键已存在，更新值
            items[i].value = value;
            return;
        }

        // 如果键不存在，插入新键值对
        if (n == items.length) resize(2 * items.length); // 如果容量不足，扩容
        for (int j = n; j > i; j--) {
            items[j] = items[j - 1]; // 向后移动元素
        }
        items[i] = new Item<>(key, value); // 插入新键值对
        n++;
    }

    // 删除某个键
    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException("Key cannot be null");

        int i = rank(key);
        if (i < n && items[i].key.equals(key)) {
            for (int j = i; j < n - 1; j++) {
                items[j] = items[j + 1]; // 向前移动元素
            }
            items[--n] = null; // 删除最后一个元素
            if (n > 0 && n == items.length / 4) resize(items.length / 2); // 缩小容量
        }
    }

    // 返回小于指定键的键值对数量
    private int rank(Key key) {
        int lo = 0, hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(items[mid].key);
            if (cmp < 0) hi = mid - 1;
            else if (cmp > 0) lo = mid + 1;
            else return mid;
        }
        return lo;
    }

    // 调整数组大小
    private void resize(int capacity) {
        Item<Key, Value>[] temp = (Item<Key, Value>[]) new Item[capacity];
        for (int i = 0; i < n; i++) {
            temp[i] = items[i];
        }
        items = temp;
    }

    // 归并排序实现
    private void mergeSort(Item<Key, Value>[] array, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        mergeSort(array, lo, mid);
        mergeSort(array, mid + 1, hi);
        merge(array, lo, mid, hi);
    }

    private void merge(Item<Key, Value>[] array, int lo, int mid, int hi) {
        Item<Key, Value>[] aux = Arrays.copyOf(array, array.length); // 辅助数组
        int i = lo, j = mid + 1;

        for (int k = lo; k <= hi; k++) {
            if (i > mid) array[k] = aux[j++];
            else if (j > hi) array[k] = aux[i++];
            else if (aux[j].key.compareTo(aux[i].key) < 0) array[k] = aux[j++];
            else array[k] = aux[i++];
        }
    }

    // 测试代码
    public static void main(String[] args) {
        // 创建一个 Item 数组
        Item<String, Integer>[] inputItems = new Item[] {
                new Item<>("E", 5),
                new Item<>("A", 1),
                new Item<>("S", 19),
                new Item<>("Y", 25),
                new Item<>("Q", 17),
                new Item<>("U", 21)
        };

        // 使用构造函数对数组进行排序
        BinarySearchSTItem<String, Integer> st = new BinarySearchSTItem<>(inputItems);

        // 打印排序后的键值对
        for (int i = 0; i < st.size(); i++) {
            System.out.println(st.items[i].key + " -> " + st.items[i].value);
        }

        // 测试插入和删除操作
        st.put("B", 2);
        System.out.println("After adding B -> 2:");
        for (int i = 0; i < st.size(); i++) {
            System.out.println(st.items[i].key + " -> " + st.items[i].value);
        }

        st.delete("S");
        System.out.println("After deleting S:");
        for (int i = 0; i < st.size(); i++) {
            System.out.println(st.items[i].key + " -> " + st.items[i].value);
        }
    }
}

/******************************************************************************
 *  Copyright 2002-2022, Robert Sedgewick and Kevin Wayne.
 *
 *  This file is part of algs4.jar, which accompanies the textbook
 *
 *      Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
 *      Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
 *      http://algs4.cs.princeton.edu
 *
 *
 *  algs4.jar is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  algs4.jar is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with algs4.jar.  If not, see http://www.gnu.org/licenses.
 ******************************************************************************/

